public class 正则表达式匹配 {
    public boolean isMatch(String ss, String pp) {
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int n = s.length;
        int m = p.length;
        int[][] dp = new int[n + 1][m + 1];// 0 没有访问过, 1 访问过为 true, 2 访问过为 false
        return dfs(s,p,0,0,dp);
    }

    private boolean dfs1(char[] s, char[] p, int i, int j,int[][] dp) {
        if (dp[i][j] != 0) {
            return dp[i][j] == 1;
        }
        boolean ans = false;
        if (s.length == i) {
            // 字符串匹配完了
            if (p.length == j) {
                // 字符规律的字符串也匹配完了
                ans = true;
                dp[i][j] = (ans == false ? 2 : 1);
                return ans;
            } else {
                // 这个元素的下一个必须是 * 才可以和上一个元素一起被抵消掉, 然后将下下个元素继续递归
                ans = j + 1 < p.length && p[j + 1] == '*' && dfs(s,p,i,j + 2,dp);
                dp[i][j] = (ans == false ? 2 : 1);
                return ans;
            }
        } else if (p.length == j) {
            dp[i][j] = (ans == false ? 2 : 1);
            return ans;
        } else {
            // 字符串还没有匹配完
            if (j + 1 < p.length && p[j + 1] == '*') {
                ans = (s[j] == '.' || s[i] == p[j]) ? dfs(s,p,i + 1,j,dp) : dfs(s,p,i,j + 2,dp);
                dp[i][j] = (ans == false ? 2 : 1);
                return ans;
            } else {
                ans = (s[j] == '.' || s[i] == p[j]) && dfs(s,p,i + 1,j + 1,dp);
                dp[i][j] = (ans == false ? 2 : 1);
                return ans;
            }
        }
    }

    private boolean dfs(char[] s, char[] p, int i, int j,int[][] dp) {
        if (dp[i][j] != 0) {
            return dp[i][j] == 1;
        }
        boolean ans = false;
        if (s.length == i) {
            // 字符串匹配完了
            if (p.length == j) {
                // 字符规律的字符串也匹配完了
                ans = true;
                dp[i][j] = (ans == false ? 2 : 1);
                return ans;
            } else {
                // 这个元素的下一个必须是 * 才可以和上一个元素一起被抵消掉, 然后将下下个元素继续递归
                ans = j + 1 < p.length && p[j + 1] == '*' && dfs(s,p,i,j + 2,dp);
                dp[i][j] = (ans == false ? 2 : 1);
                return ans;
            }
        } else if (p.length == j) {
            dp[i][j] = (ans == false ? 2 : 1);
            return ans;
        } else {
            // 字符串还没有匹配完
            if (j + 1 < p.length && p[j + 1] == '*') {
                ans = ((p[j] == '.' || s[i] == p[j]) && dfs(s,p,i + 1,j,dp)) || dfs(s,p,i,j + 2,dp);
                dp[i][j] = (ans == false ? 2 : 1);
                return ans;
            } else {
                ans = (p[j] == '.' || s[i] == p[j]) && dfs(s,p,i + 1,j + 1,dp);
                dp[i][j] = (ans == false ? 2 : 1);
                return ans;
            }
        }
    }
}
